// https://www.lintcode.com/problem/reverse-words-in-a-string/description?_from=ladder&&fromId=6

class Solution {
public:
    /*
     * @param s: A string
     * @return: A string
     */
    // string reverseWords(string &s) {
    //     string result = "";
    //     if (s.empty()) return result;
    //     int i = s.length() - 1;
    //     while (i >= 0)
    //     {
    //         while (i >= 0 && s[i] == ' ') i--;
    //         if (i < 0) break; // " "
    //         int j = i;
    //         while (j >= 0 && s[j] != ' ') j--;
    //         result += s.substr(j + 1, i - j) + ' '; // 注意加' '
    //         // if (j < 0) break; //单个word //更新i=j的话就不需要了，由i判断
    //         i = j; //注意更新
    //     }
    //     return result;
    // }
    
    // 法2：memory O(1)
    void reverse (string &s, int i, int j)
    {
        while (i < j)
        {
            char tmp = s[i];
            s[i++] = s[j];
            s[j--] = tmp;
        }
    }
    
    string reverseWords(string &s) {
        if (s.empty()) return s;
        int i = 0;
        int j = 0;
        while (i < s.length())
        {
            while (i < s.length() && s[i] == ' ') ++i;
            if (i == s.length()) break;
            int start = j;
            while (i < s.length() && s[i] != ' ') s[j++] = s[i++];
            reverse(s, start, --j);
            j++;
            if (i < s.length()) s[j++] = ' ';
        }
        if (j != 0) 
        {
            s = s.substr(0, j);
            reverse(s, 0, --j);
            return s;
        }
        else return "";
    }
};